/* Copyright (C) 2007 Free Software Foundation, Inc. 
 * See the copyright notice in the file /usr/LICENSE.
 * Created by flyan on 2020/5/24.
 * QQ: 1341662010
 * QQ-Group:909830414
 * gitee: https://gitee.com/flyanh/
 *
 * 给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
 *
 * 请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
 *
 * 你可以假设 nums1 和 nums2 不会同时为空。
 *
 * 示例 1:
 *
 * nums1 = [1, 3]
 * nums2 = [2]
 *
 * 则中位数是 2.0
 * 示例 2:
 *
 * nums1 = [1, 2]
 * nums2 = [3, 4]
 *
 * 则中位数是 (2 + 3)/2 = 2.5
 */
#include <stdio.h>
#include <malloc.h>


/* sort info */
typedef struct merge_info {
    int l, r;
} MergeInfo_t;
typedef struct heap_node_tag {
    int num;
    int segNo;
    int index;
} HeapNode_t;

/*===========================================================================*
 *		    min_heap_sink					     *
 *===========================================================================*/
void min_heap_sink(HeapNode_t ** begin, HeapNode_t ** end, int i)
{
    int child;
    HeapNode_t *initialNode = begin[i];
    for (; (i << 1) + 1 < end - begin; i = child) {
        child = (i << 1) + 1;
        if(child + 1 < end - begin) {
            /* 取子节点中最小的，如果 x 相同，再判断 y */
            if (begin[child]->num > begin[child + 1]->num)
                child++;
        }
        if (initialNode->num > begin[child]->num)
            begin[i] = begin[child];
        else
            break;
    }
    begin[i] = initialNode;
}

/*===========================================================================*
 *		    min_heap_swim					     *
 *===========================================================================*/
void min_heap_swim(HeapNode_t ** begin, int i) {
    HeapNode_t *initialNode = begin[i];
    for (; i > 0 && (initialNode->num < begin[(i - 1) >> 1]->num); i = (i - 1) >> 1)
        begin[i] = begin[(i - 1) >> 1];
    begin[i] = initialNode;
}

/*===========================================================================*
 *		    make_heap					     *
 *		    建立堆
 *===========================================================================*/
inline void make_heap(HeapNode_t ** begin, HeapNode_t ** end) {
    for (int i = (end - begin) / 2 - 1; i >= 0; i--) {
        min_heap_sink(begin, end, i);
    }
}

/*===========================================================================*
 *		    push_heap					     *
 *      将序列的尾元素加入堆中，并使堆整体有序化
 *===========================================================================*/
inline void push_heap(HeapNode_t **begin, HeapNode_t **end) {
    min_heap_swim(begin, end - begin - 1);
}

/*===========================================================================*
 *		    pop_heap					     *
 *      将堆顶元素移出堆，并使剩下部分有序化
 *===========================================================================*/
inline void pop_heap(HeapNode_t **begin, HeapNode_t **end) {
    HeapNode_t *tempNode = *begin;
    *begin = *(end - 1);
    *(end - 1) = tempNode;
    min_heap_sink(begin, end - 1, 0);
}

/*===========================================================================*
 *		    magic_merge					     *
 *		   归并多线程排序的结果
 *===========================================================================*/
void magic_merge(const int *in, int *out, MergeInfo_t *info) {
    int i;
    HeapNode_t *minHeap[2];
    int heap_size = 2;

    for (i = 0; i < heap_size; ++i) {
        minHeap[i] = (HeapNode_t *) malloc(sizeof(HeapNode_t));
        minHeap[i]->num = in[info[i].l];
        minHeap[i]->segNo = i;
        minHeap[i]->index = info[i].l;
    }

    make_heap(minHeap, minHeap + heap_size);
    i = 0;
    while(heap_size)
    {
        pop_heap(minHeap, minHeap + heap_size);
        out[i] = minHeap[heap_size - 1]->num;
        i++;

        if(++minHeap[heap_size - 1]->index <= info[minHeap[heap_size - 1]->segNo].r) {
            minHeap[heap_size - 1]->num = in[minHeap[heap_size - 1]->index];
            push_heap(minHeap, minHeap + heap_size);
        }
        else heap_size--;
    }
}

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
    /* 先将两个有序的数组归并成一个新的有序的数组 */
    int i;
    const int total_size = nums1Size + nums2Size;
    int in_nums[total_size];
    int out_nums[total_size];
    for(i = 0; i < nums1Size; ++i) in_nums[i] = nums1[i];
    for(i = nums1Size; i < total_size; ++i) in_nums[i] = nums2[i - nums1Size];
    int *nums = in_nums;
    if(nums1Size && nums2Size) {    /* 两个数组都存在时我们才进行归并堆排序 */
        MergeInfo_t infos[2] = {
                { 0, nums1Size - 1 },
                { nums1Size, total_size - 1 }
        };
        magic_merge(in_nums, out_nums, infos);
        nums = out_nums;
    }


    /* 根据数组长度奇偶性来计算中位数 */
    int mid = total_size >> 1;
    if(total_size & 1)    /* 奇数 */
        return nums[mid];
    else           /* 偶数 */
        return (nums[mid - 1] + nums[mid]) / 2.0;
}

int main(void) {
    int nums1[] = { };
    int nums2[] = { 1 };
    double ans = findMedianSortedArrays(nums1, 0, nums2, 1);
    printf("中位数： %3f\n", ans);
}

